package top.humbleyuan.double_pointer;

import java.util.Arrays;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:02
 * @Des 颜色分类
 */
public class LeetCode_75 {
    public static void main(String[] args) {
        int[] nums = {2, 0, 2, 1, 1, 0};

        // 双指针,分别记录前后第一个不是0和1的index
        int curZeroIndex = 0;
        int curTwoIndex = nums.length - 1;

        for (int i = 0; i < nums.length; i++) {

            if ((nums[i] == 0) && (i == curZeroIndex)) {
                curZeroIndex++;
                continue;
            }

            if ((nums[i] == 2) && (i > curTwoIndex)) {
                break;
            }

            // 和最前面不是0的交换
            if (nums[i] == 0 && i != curZeroIndex) {
                int temp = nums[i];
                nums[i] = nums[curZeroIndex];
                nums[curZeroIndex++] = temp;
                i--;
            }

            if (nums[i] == 2 && i != curTwoIndex) {
                int temp = nums[i];
                nums[i] = nums[curTwoIndex];
                nums[curTwoIndex--] = temp;
                i--;
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}
